#pragma once
#include <iostream>

using std::cout;
using std::endl;

template <class T>
struct BSTreeNode
{
    BSTreeNode* _left;
    BSTreeNode* _right;
    T _val;
    BSTreeNode(const T& val)
        : _left(nullptr),
        _right(nullptr),
        _val(val)
    {}
};

template <class T>
class BinarySearchTree
{
    typedef BSTreeNode<T> Node;

public:

    BinarySearchTree()
    {}

    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }

    bool Find(const T& val)
    {
        Node* cur = _root;
        while (cur)
        {
            if (val > cur->_val)cur = cur->_right;
            else if (val < cur->_val)cur = cur->_left;
            else return true;
        }
        return false;
    }

    bool Erase(const T& val)
    {
        Node* cur = _root, * parent = nullptr;
        while (cur)
        {
            if (val > cur->_val)parent = cur, cur=cur->_right;
            else if (val < cur->_val)parent = cur, cur=cur->_left;
            else
            {
                //val没有子节点 || val有一个子节点
                if (cur->_left == nullptr)
                {
                    if (cur != _root)
                    {
                        //连接父结点与cur子节点
                        if (cur->_val > parent->_val)parent->_right = cur->_right;
                        else parent->_left = cur->_right;
                    }
                    else _root = cur->_right;
                }
                else if (cur->_right == nullptr)
                {
                    if (cur != _root)
                    {
                        //连接父结点与cur子节点
                        if (cur->_val > parent->_val)parent->_right = cur->_left;
                        else parent->_left = cur->_left;
                    }
                    else _root = cur->_left;
                }
                //val有两个子节点
                else
                {
                    //将cur的val与左子树的最大val结点，或与右子树的最小val结点 对换
                    Node* left_max = cur->_left, * parent = cur;
                    while (left_max->_right)
                        parent = left_max, left_max=left_max->_right;
                    //跳出while循环后，left_max是左子树的最大val结点
                    std::swap(cur->_val, left_max->_val);
                    //把parent的右子树置空
                    parent->_right = nullptr;

                    cur=left_max;//改变cur指向
                }
                //删除cur结点
                delete cur;
                return true;
            }
        }
        return false;
    }

    bool Insert(const T& val)
    {
        if (_root == nullptr)
            _root = new Node(val);
        // 注意BSTree的特点：左子树<根<右子树
        Node* cur = _root, * parent = nullptr;
        while (cur)
        {
            if (val < cur->_val)
                parent = cur, cur = cur->_left;
            else if (val > cur->_val)
                parent = cur, cur = cur->_right;
            else
                return false;
        }
        cur = new Node(val);
        if (val > parent->_val)
            parent->_right = cur;
        else
            parent->_left = cur;

        return true;
    }

    //递归实现
    BinarySearchTree(const BinarySearchTree& tree)
    {
        _Copy_Tree(tree._root);
    }

    BinarySearchTree& operator=(BinarySearchTree tree)
    {
        std::swap(tree._root,_root);
        return *this;
    }

    bool Find_Rcs(const T& val)
    {
        return _Find_Rcs(_root,val);
    }

    bool Insert_Rcs(const T& val)
    {
        return _Insert_Rcs(_root,val);
    }

    bool Erase_Rcs(const T& val)
    {
        return _Erase_Rcs(_root,val);
    }

    void Destroy_Rcs()
    {
        //cout<<"delete:";
        _Destroy_Rcs(_root);
        //cout<<endl;
    }

    ~BinarySearchTree()
    {
        _Destroy_Rcs(_root);
    }

private:
    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_val << " ";
        _InOrder(root->_right);
    }

    bool _Find_Rcs(Node* root,const T& val)
    {
        if(root==nullptr)
            return false;
        if(val>root->_val)
            return _Find_Rcs(root->_right,val);
        else if(val<root->_val)  
            return _Find_Rcs(root->_left,val);
        else 
            return true;
    }

    bool _Insert_Rcs(Node*& root,const T& val)//root是上一个树节点的_right或_left
    {
        //找到位置了
        if(root==nullptr)
        {
            root=new Node(val);
            return true;
        }
        else if(val>root->_val)
            return _Insert_Rcs(root->_right,val);
        else if(val<root->_val)
            return _Insert_Rcs(root->_left,val);
        else if(val==root->_val)
            return false;
    }

    bool _Erase_Rcs(Node*& root,const T& val)
    {
        //找到位置了
        if(root==nullptr)
        {
            return false;
        }
        else if(val>root->_val)
            return _Insert_Rcs(root->_right,val);
        else if(val<root->_val)
            return _Insert_Rcs(root->_left,val);
        else if(val==root->_val)
        {
            Node* cur=root;
            //判断左右子树情况
            if(root->_left==nullptr)
                root=root->_right;
            else if(root->_right==nullptr)
                root=root->_left;
            else
            {
                //左右子树都不为空，需换位操作，如：与“左子树最大值”交换
                Node* left_max=root->_left,*parent=root;
                while(left_max->_right)
                    parent=left_max,left_max=left_max->_right;
                parent->_right=nullptr;
                //交换
                std::swap(left_max->_val,cur->_val);
                cur=left_max;
            }
            delete cur;
            return true;
        }
    }

    void _Destroy_Rcs(Node* root)
    {
        if(root==nullptr)
            return;
        _Destroy_Rcs(root->_left);
        _Destroy_Rcs(root->_right);

        //cout<<root->_val<<" ";
        delete root;
    }

    void _Copy_Tree(Node* root)
    {
        if(root==nullptr)
            return;
        //前序遍历
        Insert(root->_val);
        _Copy_Tree(root->_left);
        _Copy_Tree(root->_right);
    }

private:
    Node* _root = nullptr;
};